package dsaa;

import java.io.*;

public class lab2f {
    static final long INF=(long) 6579111196L;
    public static void main(String[] args) throws IOException{
        //二分套二分A[i][j] i2+12345×i+j2−12345×j+i×j
        //当j固定，i=n时取最大值
        //外层二分：先找到假设的排第m位的数的值
        //内层二分：判断是否正确
        //数组会超内存思考不用数组的办法
        //找出最大的满足有m-1个数比其小的数（二分查找）
        StreamTokenizer input =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter print = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        input.nextToken();
        int t = (int)input.nval;
        while (t >= 1) {
            input.nextToken();
            int n = (int)input.nval;
            input.nextToken();
            long m = (long)input.nval;
            int i = 1;
            int j = 1;
            long max=INF ;
            long min =-INF;
/*
            while (j <= n) {
                if (min > fx(1,j)) {
                    min = fx(1,j);
                }
                if (max < fx(n,j)) {
                    max = fx(n,j);
                }
                j = j + 1;
            }

 */
            long mnum =0;
            int smallernum = 0;//用于记录比mnum小的数，需要为m，找到后再遍历找出排m的数字
            //找出比mnum小的数字并计数

            //外层二分
            long maxm = -1000000000;
            while (smallernum != m) {
                maxm=-1000000000;
                smallernum=0;
                //内层二分，j固定
                j = 1;
                while (j <= n) {
                    //找到j固定情况下，比mnum小的数字的下标的最大值，所以等于的情况下，还要往后找
                    int l = 1;
                    int r = n;
                    int mid = (l + r) / 2;
                    while (l <= r) {
                        if (fx(mid,j) > mnum) {
                            r = mid - 1;
                            mid = (l + r) / 2;
                        }
                        if (fx(mid,j)<=mnum) {
                            l = mid + 1;
                            mid = (l + r) / 2;
                        }
                    }
                    //l=r+1,下标应该为r

                    if (fx(r,j)> maxm&r>=1) {
                        maxm = fx(r,j);
                    }


                    smallernum = smallernum + r;
                    j = j + 1;
                }
                if (smallernum > m) {
                    //该数字偏大，要往小调整
                    max = mnum+1;
                    mnum = (max + min) / 2;
                }
                if(smallernum<m) {
                    min = mnum-1;
                    mnum = (max + min) / 2;
                }

            }
            print.println(maxm);
            print.flush();
            t=t-1;
        }
    }

    public static long fx(int i,int j){
        long fx= (long) Math.pow(i, 2) + 12345 * i + (long) Math.pow(j, 2) - 12345 * j + i * j;
        return fx;
    }
}
